CMU 15-112: Fundamentals of Programming and Computer Science
Day5 Practice (Due never)

• These problems will help you prepare for hw4 and quiz2.
• Do not use recursion.
• Do not hardcode the test cases in your solutions.

• Trace #1:
  
  def ct1(a, b): a += [3] a = a + [4] for c in a: for i in range(len(b)): if (b[i] not in a): print("A", end="") b[i] += c elif (c % 2 == 1): print("B", end="") b += [c] elif (b[-1] != c): print("C", end="") b = b + [c] return (a,b) a = [4] b = [2,3] print(ct1(a,b)) print(a,b)


• Trace #2:
  
  def ct2(L): result = [ ] M = [L[i]*10**i for i in range(len(L))] for val in M: result.extend([val, L.pop()]) return result L = [2,5,3] M = ct2(L) print(L, M)


• Trace #3:
  
  def ct3(L): result = [ ] M = L[:] # same as M = copy.copy(L) if (M == L): result.append(1) if (M is L): result.append(2) if (M[0] == L[0]): result.append(3) if (M[0] is L[0]): result.append(4) return result print(ct3([5,7,6]))


• Trace #4:
  
  def ct4(L): M = L L += [4] M = M + [5] print(L, M) ct4(list(range(1)))

• RC #1 of 2:
  
  def rc1(M): assert(isinstance(M, list) and (len(M) == 5)) for i in range(-1, 3): assert(M[i] == M[i-1] + i) return (sum(M) == 15)


• RC #2 of 2:
  
  def rc2(L): assert((isinstance(L, list)) and (None not in L)) i = 0 while (L[i] != None): j = L[i] L[i] = None i = j a = [None]*2 return (L == a + [-1] + a)

1. The Locker Problem
2. Anagrams
3. The Sieve of Eratosthenes
4. The Prime Counting Function
5. Sorting (selection, bubble, merge, builtin sorts)

6. alternatingSum(a)
   Write the function alternatingSum(a) that takes a list of numbers and returns the alternating sum (where the sign alternates from positive to negative or vice versa). For example, alternatingSum([5,3,8,4]) returns 6 (that is, 5-3+8-4).


7. median(a)
   Write the non-destructive function median(a) that takes a list of floats and returns the median value, which is the value of the middle element, or the average of the two middle elements. If the list is empty, return None.


8. isPalindromicList(a)
   Write the function isPalindromicList(a) that takes a list and returns True if it is the same forwards as backwards and False otherwise.


9. reverse(a)
   Write the function reverse(a) that destructively reverses the list a. So if a equals [2,3,4], then after reverse(a), a should equal [4,3,2]. As is generally true of destructive functions, this function does not return a value (well, technically it returns None, but Python does that for you).


10. vectorSum(a, b)
    Write the function vectorSum(a,b) that takes two same-length lists of numbers a and b, and returns a new list c where c[i] is the sum of a[i] and b[i]. For example, vectorSum([2,4],[20,30]) returns [22, 34].


11. isSorted(a)
    Write the function isSorted(a) that takes a list of numbers and returns True if the list is sorted (either smallest-first or largest-first) and False otherwise. Your function must only consider each value in the list once (so, in terms of big-oh, which we will learn soon, it runs in O(n) time, where n=len(a)), and so in particular you may not sort the list.


12. dotProduct(a, b)
    Background: the 'dot product' of the lists [1,2,3] and [4,5,6] is (1*4)+(2*5)+(3*6), or 4+10+18, or 32. In general, the dot product of two lists is the sum of the products of the corresponding terms. With this in mind, write the function dotProduct(a,b). This function takes two lists and non-destructively returns the dotProduct of those lists. If the lists are not equal length, ignore the extra elements in the longer list.


13. isRotation(a1, a2)
    Write the function isRotation(a1, a2) that takes two lists, a1 and a2, and returns True if a2 is a rotation of a1 and False otherwise. For example, [2,3,4,5,6] is a rotation of [4,5,6,2,3]. A list is a rotation of itself.


14. moveToBack(a, b)
    Write the function moveToBack(a,b) which takes two lists a and b, and destructively modifies a so that each element of a that appears in b moves to the end of a in the order that they appear in b. The rest of the elements in a should still be present in a, in the same order they were originally. The function should return a. Examples:

        moveToBack([2, 3, 3, 4, 1, 5], [3]) -> [2, 4, 1, 5, 3, 3]
        moveToBack([2, 3, 3, 4, 1, 5], [2, 3]) -> [4, 1, 5, 2, 3, 3]
        moveToBack([2, 3, 3, 4, 1, 5], [3, 2]) -> [4, 1, 5, 3, 3, 2]
    

    Do this without creating another list of length len(a).


15. binaryListToDecimal(a)
    Write the function binaryListToDecimal(a) which takes a list of 1s and 0s, and returns the integer represented by reading the list from left to right as a single binary number. Examples:

        binaryListToDecmial([1, 0]) -> 2
        binaryListToDecmial([1, 0, 1, 1]) ->11
        binaryListToDecmial([1, 1, 0, 1]) ->13
    



16. smallestDifference(a)
    Write the function smallestDifference(a) that takes a list of integers and returns the smallest absolute difference between any two integers in the list. If the list is empty, return -1.


17. split(s, delimiter)
    Write the function split(s, delimiter), without using the builtin split function (of course), that takes a string and a delimiter and returns a list of substrings that are determined by that delimiter. For example, split("ab,cd,efg", ",") returns ["ab", "cd", "efg"].


18. join(L, delimiter)
    Write the function join(L, delimiter), without using the builtin join function (of course), that takes a list and a delimiter and returns the string composed of each element in the list separated by the delimiter. So, join(["ab", "cd", "efg"], ",") returns "ab,cd,efg".


19. repeatingPattern(a)
    Write the function repeatingPattern(a) that takes a list a and returns True if a == b*k for some list b and some value k>1, and False otherwise. For example, repeatingPattern([1,2,3,1,2,3]) returns True (b==[1,2,3] and k=2).


20. mostAnagrams(wordList)
    Write the function mostAnagrams(wordList) that takes a possibly-unsorted list of words (all lowercase) and returns the first word alphabetically in the list that contains the most anagrams of itself in the list. If there are ties, still return just the first word alphabetically.


21. map(f, a)
    Write the function map(f, a), which does not use the builtin map function, and which takes a function f and a list a, and returns a new list containing f(x) for each value x in a. For example, say you defined a function plus3(x) that returns (x+3). Then, map(plus3, [2,4,7]) returns [5,7,10].


22. firstNEvenFibonacciNumbers(n)
    Write the function firstNEvenFibonacciNumbers(n) that takes a non-negative number n and returns a list of the first n even Fibonacci numbers in increasing order. For example, firstNEvenFibonacciNumbers(4) returns [2, 8, 34, 144]. Note that your answer must run in O(n) time, so it cannot repeatedly call nthEvenFibonacciNumber.


23. mostCommonName(a)
    Write the function mostCommonName, that takes a list of names (such as ['Jane', 'Aaron', 'Cindy', 'Aaron'], and returns the most common name in this list (in this case, 'Aaron'). If there is more than one such name, return a list of the most common names, in alphabetical order (actually, in whatever order sorted() uses). So mostCommonName(['Jane', 'Aaron', 'Jane', 'Cindy', 'Aaron']) returns the list ['Aaron', 'Jane']. If the list is empty, return None. Also, treat names case sensitively, so 'jane' and 'Jane' are different names.


24. histogram(a)
    Write the function histogram(a) that takes a list of integers between 0 and 100, inclusive, representing exam scores, and returns a string representing a histogram of that data. The details can be gleaned from this example: histogram([73, 62, 91, 74, 100, 77]) returns this multi-line string:

    60-69: *
    70-79: ***
    80-89:
    90++ : **
    



25. nearestWords(wordList, word)
    Write the function nearestWords(wordList, word) that takes a sorted wordlist and a single word (all words in this problem will only contain lowercase letters). If the word is in the wordlist, then that word is returned. Otherwise, the function returns a list of all the words (in order) in the wordlist that can be obtained by making a single small edit on the given word, either by adding a letter, deleting a letter, or changing a letter. If no such words exist, the function returns None.


26. bowlingScore(pinsPerThrowList)
    Background: in bowling, a bowler gets 2 throws per frame for 10 frames, where each frame begins with 10 pins freshly positioned, and the score is the sum of all the pins knocked down. However, if the bowler knocks down all 10 pins on the first throw of a frame, it is called a "strike", and they do not get a second throw in that frame; also, the number of pins knocked down in the next two throws are added to the score of that frame. Also, if the bowler knocks down the rest of the 10 pins on the second throw in a frame, that is called a "spare", and the number of pins knocked down in the next throw are added to the score of that frame. Finally, if there is a spare or strike in the final frame, then the bowler gets one extra throw in that frame (but if there is a subsequent strike, they still get only that one extra throw). With all this in mind, write the function bowlingScore that takes a list of the number of pins knocked down on each throw and returns the score. Note that throws skipped due to strikes are not listed, so the best possible result is a list of 12 10's (all strikes), which would score 300 points.


27. evalPolynomial(coeffs, x)
    Background: we can represent a polynomial as a list of its coefficients. For example, [2, 3, 0, 4] could represent the polynomial 2x3 + 3x2 + 4. With this in mind, write the function evalPolynomial(coeffs, x) that takes a list of coefficients and a value x and returns the value of that polynomial evaluated at that x value. For example, evalPolynomial([2,3,0,4], 4) returns 180 (2*43 + 3*42 + 4 = 2*64 + 3*16 + 4 = 128 + 48 + 4 = 180).


28. multiplyPolynomials(p1, p2)
    Write the function multiplyPolynomials(p1, p2) which takes two polynomials as defined in the previous problem and returns a third polynomial which is the product of the two. For example, multiplyPolynomials([2,0,3], [4,5]) represents the problem (2x**2 + 3)(4x + 5), and:
        (2x**22 + 3)(4x + 5) = 8x**3 + 10x**2 + 12x + 15
    And so this returns [8, 10, 12, 15].


29. polynomialToString(p)
    Write the function polynomialToString(p) that takes a polynomial as defined in the previous problems and returns a string representation of that polynomial, with these rules:
    • Use "n" as the variable
    • Use "^" for exponentation (though that means "bitwise-xor" in Python)
    • Include a space before/after each "+" or "-" sign
    • Do not include 0 coefficients (unless the entire polynomial equals 0)
    So polynomialToString([2,-3,0,4]) returns "2n^3 - 3n^2 + 4"


30. areaOfPolygon(L)
    Write the function areaOfPolygon(L) that takes a list of (x,y) points that are guaranteed to be in either clockwise or counter-clockwise order around a polygon, and returns the area of that polygon, as described here. For example (taken from that text), areaOfPolygon([(4,10), (9,7), (11,2), (2,2)]) returns 45.5 (at least the result is almostEqual to 45.5). Here is a sample test function for you:

    def testAreaOfPolygon():
        print("Testing areaOfPolygon()...", end="")
        assert(almostEqual(areaOfPolygon([(4,10), (9,7), (11,2), (2,2)]), 45.5))
        assert(almostEqual(areaOfPolygon([(9,7), (11,2), (2,2), (4, 10)]), 45.5))
        assert(almostEqual(areaOfPolygon([(0, 0), (0.5,1), (1,0)]), 0.5))
        assert(almostEqual(areaOfPolygon([(0, 10), (0.5,11), (1,10)]), 0.5))
        assert(almostEqual(areaOfPolygon([(-0.5, 10), (0,-11), (0.5,10)]), 10.5))
        print("Passed!")